#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/20 8:51
@Author  : Chen Liu
@FileName: pai_lie.py
@Software: PyCharm
"""


# 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
# 思路：递归，深度优先遍历

class Solution:
    def permute(self, nums):
        self.length = len(nums)
        self.re = []
        self.sub_permute(nums, temp=[])
        return self.re

    def sub_permute(self, nums, temp):
        # 如果达到递归条件
        if len(temp) == self.length:
            self.re.append(temp)
        else:
            for i in nums:
                self.sub_permute(nums[:nums.index(i)] + nums[nums.index(i)+1:], temp+[i])

    def permute_2(self, nums):
        """参考字符串的全排列"""
        # 递归终止条件
        if len(nums) <= 1:
            return [nums]
        re = []
        for i in range(len(nums)):
            # 将剩余的元素加到一起去
            for j in self.permute_2(nums[0:i] + nums[i + 1:]):
                re.append([nums[i]] + j)

        return re


def test(temp):
    if len(temp) == 3:
        print(temp)
    else:
        for i in temp:
            print(i)


if __name__ == "__main__":
    s = Solution()
    nums = [1, 2, 3]
    re = s.permute(nums)
    # re = fun1(nums)
    # print(re)
    test(nums)
